#!/bin/python
import sys, os, random, heapq, operator, collections, math, datetime, re, copy#, copy, profile, mycheck

in_file_name = None
out_file_name = None
n = 0
m = 0
problem = None


Operation = collections.namedtuple('Operation', ['time', 'job_id', 'machine_id', 'duration'])
Candidate = collections.namedtuple('Candidate', ['objective', 'permutation', 'schedule'])
Interval = collections.namedtuple('Interval', ['start', 'end'])


def copy_candidate(candidate):
    permutation_copy = []
    for i in candidate.permutation:
        permutation_copy.append(i)

    schedule_copy = []
    for resource in candidate.schedule:
        resource_copy = []
        for job in resource:
            resource_copy.append(Operation(job.time, job.job_id, job.machine_id, job.duration))
        schedule_copy.append(resource_copy)
    return Candidate(candidate.objective, permutation_copy, schedule_copy)


def take(slack, position, duration):
    if not fits(slack, position, duration):
        raise ArithmeticError
    slacks = []
    if position > slack.start:
        slacks.append(Interval(slack.start, position))
    if position + duration < slack.end:
        slacks.append(Interval(position + duration, slack.end))
    return slacks


def fits(slack, position, duration):
    return position + duration <= slack.end


def create_problem(infile):
    global n, m, problem
    problem_description = infile.readline()
    n, m = infile.readline().split()
    n = int(n)
    m = int(m)
    problem = []
    for job_id, line in enumerate(infile):
        if not line.isspace():
            line_iter = iter(line.split())
            sequence = []
            for r in xrange(m):
                machine_id = int(line_iter.next())
                duration = int(line_iter.next())
                operation = Operation(None, job_id, machine_id, duration)
                sequence.append(operation)
            problem.append(sequence)


def random_candidate():
    rperm = [i for i in range(n)]
    random.shuffle(rperm)
    schedule = pack(rperm)
    return Candidate(objective(schedule), rperm, schedule)


def pack(permutation):
    append = list.append
    resource_slacks = [ [Interval(0, sys.maxint) ] for j in xrange(m)]
    est = [0 for i in xrange(n)]
    machines = [list() for j in xrange(m)]
    for i in permutation:
        sequence = problem[i]
        for job in sequence:
            slacks = resource_slacks[job.machine_id]
            resource = machines[job.machine_id]
            for idx, slack in enumerate(slacks):
                t = max(est[job.job_id], slack.start)
                if fits(slack, t, job.duration):
                    resource_slacks[job.machine_id] = slacks[0:idx] + take(slack, t, job.duration) + slacks[idx + 1:]
                    append(resource, Operation(t, job.job_id, job.machine_id, job.duration))
                    est[job.job_id] = t + job.duration
                    break
    return [sorted(resource) for resource in machines]


def makespan(candidate):
    """ Cmax or makespan """
    return max(map(lambda operation: operation.time + operation.duration, map(operator.itemgetter(-1), candidate)))

def twft(candidate):
    """ Total weighted flow time """
    return sum(map(lambda operation: operation.time + operation.duration, map(operator.itemgetter(-1), candidate)))


def pretty_print(candidate):
    """ Pretty print
    """
    overlap = []
    for resource in candidate:
        time = 0
        for idx, job in enumerate(resource):
            if job.time < time:
                overlap.append((resource[idx-1], job))
            while job.time > time:
                sys.stdout.write(' ')
                time += 1
            for i in xrange(job.duration):
                sys.stdout.write(str(job.job_id))
                time += 1
        sys.stdout.write('\n')
    print '(%s)' % objective(candidate)
    print overlap


def neighbors(p):
    neighs = []
    for idx in range(len(p) - 1):
        q = p[:]
        q[idx], q[idx + 1] = q[idx + 1], q[idx]
        neighs.append(q)
    return neighs


def accept(D, T):
    P = math.exp(-float(D) / (float(T)+0.01))
    r = random.random()
    if r < P:
        return True
    else:
        return False


def anneal(current, its):
    best = current
    for T in xrange(its * (m + n), 1, -1):
        neighs = neighbors(current.permutation)
        perm = neighs[random.randrange(len(neighs))]
        schedule = pack(perm)
        nxt = Candidate(objective(schedule), perm, schedule)
        D = nxt.objective - current.objective
        if accept(D, float(T)/float(its)):
            current = nxt
        if current.objective < best.objective:
            best = copy_candidate(current)
            save(best, 'anneal', float(T)/float(its))
    return best


def save(best, cause, temp):
    print 'Time:%s \t Makespan:%s T:%s Cause:%s' % (datetime.datetime.now(), best.objective, temp, cause)
    with open(out_file_name, 'w') as out_file:
        out_file.write(str(makespan(best.schedule)) + ' ' + str(twft(best.schedule)) + '\n')
        for resource in best.schedule:
            for op in resource:
                out_file.write(str(op.job_id) + ' ' + str(op.time) + ' ')
            out_file.write('\n')


def record_data(best, pop_size):
    fname = copy.copy(in_file_name)
    fname = re.sub('cs540-jsp/', '', fname)
    fname = re.sub('.inst.txt', '', fname)
    fname = re.sub('.txt', '', fname)
    with open("sa_experiment_50.txt", 'a') as exp:
        exp.write('%s,%s,%s,(%s x %s)\n' % (fname, str(best.objective), str(pop_size), str(n), str(m)))


if __name__ == '__main__':
    if len(sys.argv) == 4:
        program_name, in_file_name, out_file_name, obj_function = sys.argv
    else:
        print 'Program requires 3 arguments: <input_file>, <output_file>, <objective function{0,1}>'
        os._exit(0)
    if obj_function == '0':
        objective = makespan
    elif obj_function == '1':
        objective = twft
    else:
        objective = makespan

    with open(in_file_name) as in_file:
        create_problem(in_file)

    best = random_candidate()
    for i in range(1):
        print '------------------------------------------------------------------------'
        asolution = anneal(random_candidate(), 50 * (m + n))
        if asolution.objective < best.objective:
            best = copy_candidate(asolution)
            save(best, 'iteration', 0)
    record_data(best, 50 * (m + n))
    #mycheck.check(in_file_name, out_file_name)
